home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Add-Ons / MPW / MPW re2c 1.1 / actions.cc next >
Text File  |  1995-09-08  |  10KB  |  513 lines
  1. // $Log: actions.cc,v $
  2. //Revision 1.1  1994/04/08  15:27:59  peter
  3. //Initial revision
  4. //
  5.  
  6. #include <time.h>
  7. #include <string.h>
  8. #include <iostream.h>
  9. #include <iomanip.h>
  10.  
  11. #include "globals.h"
  12. #include "parser.h"
  13. #include "dfa.h"
  14.  
  15. Symbol *Symbol::first = NULL;
  16.  
  17. Symbol::Symbol(const SubStr &str) : next(first), name(str), re(NULL) {
  18.     first = this;
  19. }
  20.  
  21. Symbol *Symbol::find(const SubStr &str){
  22.     for(Symbol *sym = first; sym; sym = sym->next)
  23.     if(sym->name == str) return sym;
  24.     return new Symbol(str);
  25. }
  26.  
  27. void showIns(ostream &o, const Ins &i, const Ins &base){
  28.     o.width(3);
  29.     o << &i - &base << ": ";
  30.     switch(i.i.tag){
  31.     case CHAR: {
  32.     o << "match ";
  33.     for(const Ins *j = &(&i)[1]; j < (Ins*) i.i.link; ++j)
  34.         prtCh(o, j->c.value);
  35.     break;
  36.     } case GOTO:
  37.     o << "goto " << ((Ins*) i.i.link - &base);
  38.     break;
  39.     case FORK:
  40.     o << "fork " << ((Ins*) i.i.link - &base);
  41.     break;
  42.     case CTXT:
  43.     o << "term " << ((RuleOp*) i.i.link)->accept;
  44.     break;
  45.     case TERM:
  46.     o << "term " << ((RuleOp*) i.i.link)->accept;
  47.     break;
  48.     }
  49.     o << "\n";
  50. }
  51.  
  52. uint RegExp::fixedLength(){
  53.     return ~0;
  54. }
  55.  
  56. char *NullOp::type = "NullOp";
  57.  
  58. void NullOp::calcSize(Char*){
  59.     size = 0;
  60. }
  61.  
  62. uint NullOp::fixedLength(){
  63.     return 0;
  64. }
  65.  
  66. void NullOp::compile(Char*, Ins*){
  67.     ;
  68. }
  69.  
  70. void NullOp::split(CharSet&){
  71.     ;
  72. }
  73.  
  74. ostream& operator<<(ostream &o, const Range &r){
  75.     if((r.ub - r.lb) == 1){
  76.     prtCh(o, r.lb);
  77.     } else {
  78.     prtCh(o, r.lb); o << "-"; prtCh(o, r.ub-1);
  79.     }
  80.     return o << r.next;
  81. }
  82.  
  83. Range *doUnion(Range *r1, Range *r2){
  84.     Range *r, **rP = &r;
  85.     for(;;){
  86.     Range *s;
  87.     if(r1->lb <= r2->lb){
  88.         s = new Range(*r1);
  89.     } else {
  90.         s = new Range(*r2);
  91.     }
  92.     *rP = s;
  93.     rP = &s->next;
  94.     for(;;){
  95.         if(r1->lb <= r2->lb){
  96.         if(r1->lb > s->ub)
  97.             break;
  98.         if(r1->ub > s->ub)
  99.             s->ub = r1->ub;
  100.         if(!(r1 = r1->next)){
  101.             uint ub = 0;
  102.             for(; r2 && r2->lb <= s->ub; r2 = r2->next)
  103.             ub = r2->ub;
  104.             if(ub > s->ub)
  105.             s->ub = ub;
  106.             *rP = r2;
  107.             return r;
  108.         }
  109.         } else {
  110.         if(r2->lb > s->ub)
  111.             break;
  112.         if(r2->ub > s->ub)
  113.             s->ub = r2->ub;
  114.         if(!(r2 = r2->next)){
  115.             uint ub = 0;
  116.             for(; r1 && r1->lb <= s->ub; r1 = r1->next)
  117.             ub = r1->ub;
  118.             if(ub > s->ub)
  119.             s->ub = ub;
  120.             *rP = r1;
  121.             return r;
  122.         }
  123.         }
  124.     }
  125.     }
  126.     *rP = NULL;
  127.     return r;
  128. }
  129.  
  130. Range *doDiff(Range *r1, Range *r2){
  131.     Range *r, *s, **rP = &r;
  132.     for(; r1; r1 = r1->next){
  133.     uint lb = r1->lb;
  134.     for(; r2 && r2->ub <= r1->lb; r2 = r2->next);
  135.     for(; r2 && r2->lb <  r1->ub; r2 = r2->next){
  136.         if(lb < r2->lb){
  137.         *rP = s = new Range(lb, r2->lb);
  138.         rP = &s->next;
  139.         }
  140.         if((lb = r2->ub) >= r1->ub)
  141.         goto noMore;
  142.     }
  143.     *rP = s = new Range(lb, r1->ub);
  144.     rP = &s->next;
  145.     noMore:;
  146.     }
  147.     *rP = NULL;
  148.     return r;
  149. }
  150.  
  151. MatchOp *merge(MatchOp *m1, MatchOp *m2){
  152.     if(!m1)
  153.     return m2;
  154.     if(!m2)
  155.     return m1;
  156.     return new MatchOp(doUnion(m1->match, m2->match));
  157. }
  158.  
  159. char *MatchOp::type = "MatchOp";
  160.  
  161. void MatchOp::display(ostream &o) const{
  162.     o << match;
  163. }
  164.  
  165. void MatchOp::calcSize(Char *rep){
  166.     size = 1;
  167.     for(Range *r = match; r; r = r->next)
  168.     for(uint c = r->lb; c < r->ub; ++c)
  169.         if(rep[c] == c)
  170.         ++size;
  171. }
  172.  
  173. uint MatchOp::fixedLength(){
  174.     return 1;
  175. }
  176.  
  177. void MatchOp::compile(Char *rep, Ins *i){
  178.     i->i.tag = CHAR;
  179.     i->i.link = &i[size];
  180.     Ins *j = &i[1];
  181.     uint bump = size;
  182.     for(Range *r = match; r; r = r->next){
  183.     for(uint c = r->lb; c < r->ub; ++c){
  184.         if(rep[c] == c){
  185.         j->c.value = c;
  186.         j->c.bump = --bump;
  187.         j++;
  188.         }
  189.     }
  190.     }
  191. }
  192.  
  193. void MatchOp::split(CharSet &s){
  194.     for(Range *r = match; r; r = r->next){
  195.     for(uint c = r->lb; c < r->ub; ++c){
  196.         CharPtn *x = s.rep[c], *a = x->nxt;
  197.         if(!a){
  198.         if(x->card == 1)
  199.             continue;
  200.         x->nxt = a = s.freeHead;
  201.         if(!(s.freeHead = s.freeHead->nxt))
  202.             s.freeTail = &s.freeHead;
  203.         a->nxt = NULL;
  204.         x->fix = s.fix;
  205.         s.fix = x;
  206.         }
  207.         if(--(x->card) == 0){
  208.         *s.freeTail = x;
  209.         *(s.freeTail = &x->nxt) = NULL;
  210.         }
  211.         s.rep[c] = a;
  212.         ++(a->card);
  213.     }
  214.     }
  215.     for(; s.fix; s.fix = s.fix->fix)
  216.     if(s.fix->card)
  217.         s.fix->nxt = NULL;
  218. }
  219.  
  220. RegExp *mkDiff(RegExp *e1, RegExp *e2){
  221.     MatchOp *m1, *m2;
  222.     if(!(m1 = (MatchOp*) e1->isA(MatchOp::type)))
  223.     return NULL;
  224.     if(!(m2 = (MatchOp*) e2->isA(MatchOp::type)))
  225.     return NULL;
  226.     Range *r = doDiff(m1->match, m2->match);
  227.     return r? (RegExp*) new MatchOp(r) : (RegExp*) new NullOp;
  228. }
  229.  
  230. RegExp *doAlt(RegExp *e1, RegExp *e2){
  231.     if(!e1)
  232.     return e2;
  233.     if(!e2)
  234.     return e1;
  235.     return new AltOp(e1, e2);
  236. }
  237.  
  238. RegExp *mkAlt(RegExp *e1, RegExp *e2){
  239.     AltOp *a;
  240.     MatchOp *m1, *m2;
  241.     if(a = (AltOp*) e1->isA(AltOp::type)){
  242.     if(m1 = (MatchOp*) a->exp1->isA(MatchOp::type))
  243.         e1 = a->exp2;
  244.     } else if(m1 = (MatchOp*) e1->isA(MatchOp::type)){
  245.         e1 = NULL;
  246.     }
  247.     if(a = (AltOp*) e2->isA(AltOp::type)){
  248.     if(m2 = (MatchOp*) a->exp1->isA(MatchOp::type))
  249.         e2 = a->exp2;
  250.     } else if(m2 = (MatchOp*) e2->isA(MatchOp::type)){
  251.         e2 = NULL;
  252.     }
  253.     return doAlt(merge(m1, m2), doAlt(e1, e2));
  254. }
  255.  
  256. char *AltOp::type = "AltOp";
  257.  
  258. void AltOp::calcSize(Char *rep){
  259.     exp1->calcSize(rep);
  260.     exp2->calcSize(rep);
  261.     size = exp1->size + exp2->size + 2;
  262. }
  263.  
  264. uint AltOp::fixedLength(){
  265.     uint l1 = exp1->fixedLength();
  266.     uint l2 = exp1->fixedLength();
  267.     if(l1 != l2 || l1 == ~0)
  268.     return ~0;
  269.     return l1;
  270. }
  271.  
  272. void AltOp::compile(Char *rep, Ins *i){
  273.     i->i.tag = FORK;
  274.     Ins *j = &i[exp1->size + 1];
  275.     i->i.link = &j[1];
  276.     exp1->compile(rep, &i[1]);
  277.     j->i.tag = GOTO;
  278.     j->i.link = &j[exp2->size + 1];
  279.     exp2->compile(rep, &j[1]);
  280. }
  281.  
  282. void AltOp::split(CharSet &s){
  283.     exp1->split(s);
  284.     exp2->split(s);
  285. }
  286.  
  287. char *CatOp::type = "CatOp";
  288.  
  289. void CatOp::calcSize(Char *rep){
  290.     exp1->calcSize(rep);
  291.     exp2->calcSize(rep);
  292.     size = exp1->size + exp2->size;
  293. }
  294.  
  295. uint CatOp::fixedLength(){
  296.     uint l1, l2;
  297.     if((l1 = exp1->fixedLength()) != ~0 &&
  298.        (l2 = exp2->fixedLength()) != ~0)
  299.     return l1+l2;
  300.     return ~0;
  301. }
  302.  
  303. void CatOp::compile(Char *rep, Ins *i){
  304.     exp1->compile(rep, &i[0]);
  305.     exp2->compile(rep, &i[exp1->size]);
  306. }
  307.  
  308. void CatOp::split(CharSet &s){
  309.     exp1->split(s);
  310.     exp2->split(s);
  311. }
  312.  
  313. char *CloseOp::type = "CloseOp";
  314.  
  315. void CloseOp::calcSize(Char *rep){
  316.     exp->calcSize(rep);
  317.     size = exp->size + 1;
  318. }
  319.  
  320. void CloseOp::compile(Char *rep, Ins *i){
  321.     exp->compile(rep, &i[0]);
  322.     i += exp->size;
  323.     i->i.tag = FORK;
  324.     i->i.link = &i[-exp->size];
  325. }
  326.  
  327. void CloseOp::split(CharSet &s){
  328.     exp->split(s);
  329. }
  330.  
  331. RegExp *expr(Scanner &);
  332.  
  333. uchar unescape(SubStr &s){
  334.     s.len--;
  335.     uchar c;
  336.     if((c = *s.str++) != '\\' || s.len == 0)
  337.     return xlat[c];
  338.     s.len--;
  339.     switch(c = *s.str++){
  340.     case 'n':
  341.     return xlat['\n'];
  342.     case 't':
  343.     return xlat['\t'];
  344.     case 'v':
  345.     return xlat['\v'];
  346.     case 'b':
  347.     return xlat['\b'];
  348.     case 'r':
  349.     return xlat['\r'];
  350.     case 'f':
  351.     return xlat['\f'];
  352.     case 'a':
  353.     return xlat['\a'];
  354.     case '0': case '1': case '2': case '3':
  355.     case '4': case '5': case '6': case '7': {
  356.     uchar v = c - '0';
  357.     for(; s.len != 0 && '0' <= (c = *s.str) && c <= '7'; s.len--, s.str++)
  358.         v = v*8 + (c - '0');
  359.     return v;
  360.     } default:
  361.     return xlat[c];
  362.     }
  363. }
  364.  
  365. Range *getRange(SubStr &s){
  366.     uchar lb = unescape(s), ub;
  367.     if(s.len < 2 || *s.str != '-'){
  368.     ub = lb;
  369.     } else {
  370.     s.len--; s.str++;
  371.     ub = unescape(s);
  372.     if(ub < lb){
  373.         uchar tmp;
  374.         tmp = lb; lb = ub; ub = tmp;
  375.     }
  376.     }
  377.     return new Range(lb, ub+1);
  378. }
  379.  
  380. RegExp *matchChar(uint c){
  381.     return new MatchOp(new Range(c, c+1));
  382. }
  383.  
  384. RegExp *strToRE(SubStr s){
  385.     s.len -= 2; s.str += 1;
  386.     if(s.len == 0)
  387.     return new NullOp;
  388.     RegExp *re = matchChar(unescape(s));
  389.     while(s.len > 0)
  390.     re = new CatOp(re, matchChar(unescape(s)));
  391.     return re;
  392. }
  393.  
  394. RegExp *ranToRE(SubStr s){
  395.     s.len -= 2; s.str += 1;
  396.     if(s.len == 0)
  397.     return new NullOp;
  398.     Range *r = getRange(s);
  399.     while(s.len > 0)
  400.     r = doUnion(r, getRange(s));
  401.     return new MatchOp(r);
  402. }
  403.  
  404. char *RuleOp::type = "RuleOp";
  405.  
  406. RuleOp::RuleOp(RegExp *e, RegExp *c, Token *t, uint a)
  407.     : ins(NULL), exp(e), ctx(c), code(t), accept(a) {
  408.     ;
  409. }
  410.  
  411. void RuleOp::calcSize(Char *rep){
  412.     exp->calcSize(rep);
  413.     ctx->calcSize(rep);
  414.     size = exp->size + ctx->size + 1;
  415. }
  416.  
  417. void RuleOp::compile(Char *rep, Ins *i){
  418.     ins = i;
  419.     exp->compile(rep, &i[0]);
  420.     i += exp->size;
  421.     ctx->compile(rep, &i[0]);
  422.     i += ctx->size;
  423.     i->i.tag = TERM;
  424.     i->i.link = this;
  425. }
  426.  
  427. void RuleOp::split(CharSet &s){
  428.     exp->split(s);
  429.     ctx->split(s);
  430. }
  431.  
  432. extern void printSpan(ostream&, uint, uint);
  433.  
  434. void optimize(Ins *i){
  435.     while(!isMarked(i)){
  436.     mark(i);
  437.     if(i->i.tag == CHAR){
  438.         i = (Ins*) i->i.link;
  439.     } else if(i->i.tag == GOTO || i->i.tag == FORK){
  440.         Ins *target = (Ins*) i->i.link;
  441.         optimize(target);
  442.         if(target->i.tag == GOTO)
  443.         i->i.link = target->i.link == target? i : target;
  444.         if(i->i.tag == FORK){
  445.         Ins *follow = (Ins*) &i[1];
  446.         optimize(follow);
  447.         if(follow->i.tag == GOTO && follow->i.link == follow){
  448.             i->i.tag = GOTO;
  449.         } else if(i->i.link == i){
  450.             i->i.tag = GOTO;
  451.             i->i.link = follow;
  452.         }
  453.         }
  454.         return;
  455.     } else {
  456.         ++i;
  457.     }
  458.     }
  459. }
  460.  
  461. void genCode(ostream& o, RegExp *re){
  462.     CharSet cs;
  463.     memset(&cs, 0, sizeof(cs));
  464.     
  465.     uint j;
  466.     
  467.     for(j = 0; j < nChars; ++j){
  468.     cs.rep[j] = &cs.ptn[0];
  469.     cs.ptn[j].nxt = &cs.ptn[j+1];
  470.     }
  471.     cs.freeHead = &cs.ptn[1];
  472.     *(cs.freeTail = &cs.ptn[nChars-1].nxt) = NULL;
  473.     cs.ptn[0].card = nChars;
  474.     cs.ptn[0].nxt = NULL;
  475.     re->split(cs);
  476. /*
  477.     for(uint k = 0; k < nChars;){
  478.     for(j = k; ++k < nChars && cs.rep[k] == cs.rep[j];);
  479.     printSpan(cerr, j, k);
  480.     cerr << "\t" << cs.rep[j] - &cs.ptn[0] << endl;
  481.     }
  482. */
  483.     Char rep[nChars];
  484.     for(j = 0; j < nChars; ++j){
  485.     if(!cs.rep[j]->nxt)
  486.         cs.rep[j]->nxt = &cs.ptn[j];
  487.     rep[j] = (Char) (cs.rep[j]->nxt - &cs.ptn[0]);
  488.     }
  489.  
  490.     re->calcSize(rep);
  491.     Ins *ins = new Ins[re->size+1];
  492.     memset(ins, 0, (re->size+1)*sizeof(Ins));
  493.     re->compile(rep, ins);
  494.     Ins *eoi = &ins[re->size];
  495.     eoi->i.tag = GOTO;
  496.     eoi->i.link = eoi;
  497.  
  498.     optimize(ins);
  499.     for(j = 0; j < re->size;){
  500.     unmark(&ins[j]);
  501.     if(ins[j].i.tag == CHAR){
  502.         j = (Ins*) ins[j].i.link - ins;
  503.     } else {
  504.         j++;
  505.     }
  506.     }
  507.  
  508.     DFA *dfa = new DFA(ins, re->size, 0, 256, rep);
  509.     dfa->emit(o);
  510.     delete dfa;
  511.     delete ins;
  512. }
  513.